|
Branch and bound (BB or B&B) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as general real valued problems. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores ''branches'' of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated ''bounds'' on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm. The algorithm depends on the efficient estimation of the lower and upper bounds of a region/branch of the search space and approaches exhaustive enumeration as the size (-dimensional volume) of the region tends to zero. The method was first proposed by A. H. Land and A. G. Doig in 1960 for discrete programming, and has become the most commonly used tool for solving NP-hard optimization problems.〔 The name "branch and bound" first occurred in the work of Little ''et al.'' on the traveling salesman problem.〔 ==Overview== The goal of a branch-and-bound algorithm is to find a value that maximizes or minimizes the value of a real-valued function , called an objective function, among some set of admissible, or candidate solutions. The set is called the search space, or feasible region. The rest of this section assumes that minimization of is desired; this assumption comes without loss of generality, since one can find the maximum value of by finding the minimum of . A B&B algorithm operates according to two principles: * It recursively splits the search space into smaller spaces, then minimizing on these smaller spaces; the splitting is called ''branching''. * Branching alone would amount to brute-force enumeration of candidate solutions and testing them all. To improve on the performance of brute-force search, a B&B algorithm keeps track of ''bounds'' on the minimum that it is trying to find, and uses these bounds to "prune" the search space, eliminating candidate solutions that it can prove will not contain an optimal solution. Turning these principles into a concrete algorithm for a specific optimization problem requires some kind of data structure that represents of sets of candidate solutions. Such a representation is called an ''instance'' of the problem. Denote the set of candidate solutions of an instance by . The instance representation has to come with two operations: * produces two or more instances that each represent a subset of . (Typically, the subsets are disjoint to prevent the algorithm from visiting the same candidate solution twice, but this is not required. The only requirement for a correct B&B algorithm is that the optimal solution among is contained in at least one of the subsets.) * computes a lower bound on the value of any candidate solution in the space represented by , that is, for all in . * determines whether represents a single candidate solution. (Optionally, if it does not, the operation may choose to return some feasible solution from among .) Using these operations, a B&B algorithm performs a top-down recursive search through the tree of instances formed by the branch operation. Upon visiting an instance , it checks whether is greater than the upper bound for some other instance that it already visited; if so, may be safely discarded from the search and the recursion stops. This pruning step is usually implemented by maintaining a global variable that records the minimum upper bound seen among all instances examined so far. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Branch and bound」の詳細全文を読む スポンサード リンク
|